package com.yuqian.JavaSe.util.list;

public class Transform {
	public static char[] transformZH(char[] h){
		return null;
	}
	
	
	public static void main(String[] args) {
		
		String ps= "abacdababc";
		int[]  k=  getNext(ps);
		
	}
	
	public static int[] getNext(String ps) {
	    char[] p = ps.toCharArray();
	    int[] next = new int[p.length];
	    next[0] = -1;
	    int j = 0;
	    int k = -1;
	    while (j < p.length - 1) {
	       if (k == -1 || p[j] == p[k]) {
	           next[++j] = ++k;
	       } else {
	           k = next[k];
	       }
	    }
	    return next;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	//求next数组
	public static int[] getNextMy(String s){
		int k=-1;
		int j=0;
		int[] result = new int[s.length()];
		char[] ks = s.toCharArray();
		result[0]=-1;
		while(j<ks.length-1){
			if(k==-1||ks[k]==ks[j]){
				result[++j]=++k;
			}else{
				k=result[k];
			}
		}
		return result;
	}
	
	
}
